#include <bits/stdc++.h>
using namespace std;

/*
2182. 构造限制重复的字符串
已解答
中等
相关标签
相关企业
提示
给你一个字符串 s 和一个整数 repeatLimit ，用 s 中的字符构造一个新字符串 repeatLimitedString ，使任何字母 连续 出现的次数都不超过 repeatLimit 次。你不必使用 s 中的全部字符。

返回 字典序最大的 repeatLimitedString 。

如果在字符串 a 和 b 不同的第一个位置，字符串 a 中的字母在字母表中出现时间比字符串 b 对应的字母晚，则认为字符串 a 比字符串 b 字典序更大 。如果字符串中前 min(a.length, b.length) 个字符都相同，那么较长的字符串字典序更大。

 

示例 1：

输入：s = "cczazcc", repeatLimit = 3
输出："zzcccac"
解释：使用 s 中的所有字符来构造 repeatLimitedString "zzcccac"。
字母 'a' 连续出现至多 1 次。
字母 'c' 连续出现至多 3 次。
字母 'z' 连续出现至多 2 次。
因此，没有字母连续出现超过 repeatLimit 次，字符串是一个有效的 repeatLimitedString 。
该字符串是字典序最大的 repeatLimitedString ，所以返回 "zzcccac" 。
注意，尽管 "zzcccca" 字典序更大，但字母 'c' 连续出现超过 3 次，所以它不是一个有效的 repeatLimitedString 。
示例 2：

输入：s = "aababab", repeatLimit = 2
输出："bbabaa"
解释：
使用 s 中的一些字符来构造 repeatLimitedString "bbabaa"。 
字母 'a' 连续出现至多 2 次。 
字母 'b' 连续出现至多 2 次。 
因此，没有字母连续出现超过 repeatLimit 次，字符串是一个有效的 repeatLimitedString 。 
该字符串是字典序最大的 repeatLimitedString ，所以返回 "bbabaa" 。 
注意，尽管 "bbabaaa" 字典序更大，但字母 'a' 连续出现超过 2 次，所以它不是一个有效的 repeatLimitedString 。
 

提示：

1 <= repeatLimit <= s.length <= 105
s 由小写英文字母组成
*/

// 法一
class Solution {
public:
	string repeatLimitedString(string s, int repeatLimit) {
		vector<int> count(26, 0);
		for (char ch : s) {
			count[ch - 'a']++;
		}

		string ans;
		int lastChar = -1;  // 上一个字符的index
		int conssecutive = 0;   // 连续次数
		while (true) {
			int chosenChar = -1;
			// 从大到小
			for (int i = 25; i >= 0; --i) {
				// 相同就跳过一轮
				if (count[i] == 0)      continue;
				if (i == lastChar && conssecutive == repeatLimit)   continue;
				chosenChar = i;
				break;
			}
			if (chosenChar == -1)   break;  // 没有可用字符了 中断

			ans.push_back('a' + chosenChar);
			count[chosenChar]--;

			// 更新连续状态
			if (chosenChar == lastChar)     conssecutive++;
			else {
				lastChar = chosenChar;
				conssecutive = 1;
			}
		}
		return ans;
	}
};

// 法二
class Solution {
	public:
	string repeatLimitedString(string s, int repeatLimit) {
		int c[128] = {0};
		for (char a : s)
			++c[a];
		c['a' - 1]++;
		int n = s.length(), i = 0;
		int p = 'z', q = 0;
		while (i < n) {
			while (!c[p])
				--p;
			int k = min(c[p], repeatLimit - (p == q));
			q = p - 1;
			while (!c[q])
				--q;
			c[p] -= k;
			while (k--)
				s[i++] = p;
			if (q < 'a')
				break;
			s[i++] = q;
			--c[q];
		}
		s.resize(i);
		return s;
	}
};

// 法三
class Solution {
	public:
	string repeatLimitedString(string s, int repeatLimit) {
		int bu[26], i, j, t = 0;
		char ret[100010];
		memset(bu, 0, sizeof(bu));
		memset(ret, 0, sizeof(ret));
		for (char c: s) bu[c - 'a']++;
		i = 25;
		while (i >= 0) {
			j = repeatLimit;
			while (bu[i] && j) {
				ret[t++] = i + 'a';
				bu[i]--;
				j--;
			}
			if (bu[i]) {
				for (j = i - 1; j >= 0 && bu[j] == 0; j--);
				if (j < 0) break;
				ret[t++] = j + 'a';
				bu[j]--;
			} else i--;
		}

		return ret;
	}
};
